Une bibliothèque de programmes optimisés pour le calcul de la Transformée de Fourier Rapide de séquences de taille N=2n (algorithme de "Split Radix")

Parmi tous les algorithmes de transformées de Fourier, celui dit à base double ("split radix") fait partie de ceux qui nécessitent le nombre d'opérations le plus faible connu tout en gardant une structure régulière, dans le cas où le nombre de points est une puissance de 2. L'objet de cette note est tout d'abord de justifier une nouvelle programmation d'algorithmes de Transformées de Fourier, en montrant qu'il est peu probable que l'on améliore sensiblement ces nouveaux algorithmes. Ceux-ci constituant alors un optimum pratique, et étant aussi généraux que les algorithmes précédemment connus, il est logique d'en rechercher une implantation la plus efficace possible, sachant que, du point de vue du nombre d'opérations, on part de la borne la plus "saine" possible. On verra de toute façon que les gains en temps de calcul sont sensibles. Cette note décrit diverses implantations en FORTRAN et en langage C de cet algorithme. Ces implantations ont été réalisées sur une station VAX/VMS 3100, puis ensuite sur une station SUN et sur un MAC. Les temps de calcul ont étés comparés avec ceux d'une bibliothèque chaque fois que possible.96 pages, figure